home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / edit / xvisrc.zip / REGEXP.C < prev    next >
C/C++ Source or Header  |  1992-07-28  |  32KB  |  1,428 lines
  1. #ifndef lint
  2. static char *sccsid = "@(#)regexp.c    2.1 7/29/92";
  3. static char *copyright = "Copyright (c) 1986 by University of Toronto.";
  4. #endif
  5.  
  6. /***
  7.  
  8. * program name:
  9.     xvi
  10. * function:
  11.     PD version of UNIX "vi" editor, with extensions.
  12. * module name:
  13.     regexp.c
  14. * module function:
  15.     Regular expression routines.
  16. * history:
  17.     Regular expression routines by Henry Spencer.
  18.     Modfied for use with STEVIE (ST Editor for VI Enthusiasts,
  19.      Version 3.10) by Tony Andrews.
  20.     Adapted for use with Xvi by Chris & John Downey.
  21.     Original copyright notice appears below.
  22.     Please note that this is a modified version.
  23. ***/
  24.  
  25. /*
  26.  * regcomp and regexec -- regsub and regerror are elsewhere
  27.  *
  28.  *    Copyright (c) 1986 by University of Toronto.
  29.  *    Written by Henry Spencer.  Not derived from licensed software.
  30.  *
  31.  *    Permission is granted to anyone to use this software for any
  32.  *    purpose on any computer system, and to redistribute it freely,
  33.  *    subject to the following restrictions:
  34.  *
  35.  *    1. The author is not responsible for the consequences of use of
  36.  *        this software, no matter how awful, even if they arise
  37.  *        from defects in it.
  38.  *
  39.  *    2. The origin of this software must not be misrepresented, either
  40.  *        by explicit claim or by omission.
  41.  *
  42.  *    3. Altered versions must be plainly marked as such, and must not
  43.  *        be misrepresented as being the original software.
  44.  *
  45.  * Beware that some of this code is subtly aware of the way operator
  46.  * precedence is structured in regular expressions.  Serious changes in
  47.  * regular-expression syntax might require a total rethink.
  48.  *
  49.  * $Log:    regexp.c,v $
  50.  * Revision 1.2     88/04/28  08:09:45  tony
  51.  * First modification of the regexp library. Added an external variable
  52.  * 'reg_ic' which can be set to indicate that case should be ignored.
  53.  * Added a new parameter to regexec() to indicate that the given string
  54.  * comes from the beginning of a line and is thus eligible to match
  55.  * 'beginning-of-line'.
  56.  *
  57.  * xvi, version 1.7:
  58.  *
  59.  * Pb(P_ignorecase) replaces reg_ic.
  60.  *
  61.  * BWORD (beginning of word) & EWORD (end of word) implemented.
  62.  *
  63.  * Some strings passed to regerror() are altered slightly, for
  64.  * consistency with other error messages in xvi.
  65.  */
  66.  
  67. #include "xvi.h"
  68. #include "regexp.h"
  69. #include "regmagic.h"
  70.  
  71. #ifdef    MEGAMAX
  72. overlay "regexp"
  73. #endif
  74.  
  75. /*
  76.  * Exported functions.
  77.  */
  78. int    cstrncmp P((char *s1, char *s2, int n));
  79. char    *cstrchr P((char *s, int c));
  80.  
  81. /*
  82.  * The "internal use only" fields in regexp.h are present to pass info from
  83.  * compile to execute that permits the execute phase to run lots faster on
  84.  * simple cases.  They are:
  85.  *
  86.  * regstart    char that must begin a match; '\0' if none obvious
  87.  * reganch    is the match anchored (at beginning-of-line only)?
  88.  * regmust    string (pointer into program) that match must include, or NULL
  89.  * regmlen    length of regmust string
  90.  *
  91.  * Regstart and reganch permit very fast decisions on suitable starting points
  92.  * for a match, cutting down the work a lot.  Regmust permits fast rejection
  93.  * of lines that cannot possibly match.     The regmust tests are costly enough
  94.  * that regcomp() supplies a regmust only if the r.e. contains something
  95.  * potentially expensive (at present, the only such thing detected is * or +
  96.  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
  97.  * supplied because the test in regexec() needs it and regcomp() is computing
  98.  * it anyway.
  99.  */
  100.  
  101. /*
  102.  * Structure for regexp "program".  This is essentially a linear encoding
  103.  * of a nondeterministic finite-state machine (aka syntax charts or
  104.  * "railroad normal form" in parsing technology).  Each node is an opcode
  105.  * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
  106.  * all nodes except BRANCH implement concatenation; a "next" pointer with
  107.  * a BRANCH on both ends of it is connecting two alternatives.    (Here we
  108.  * have one of the subtle syntax dependencies:    an individual BRANCH (as
  109.  * opposed to a collection of them) is never concatenated with anything
  110.  * because of operator precedence.)  The operand of some types of node is
  111.  * a literal string; for others, it is a node leading into a sub-FSM.  In
  112.  * particular, the operand of a BRANCH node is the first node of the branch.
  113.  * (NB this is *not* a tree structure:    the tail of the branch connects
  114.  * to the thing following the set of BRANCHes.)     The opcodes are:
  115.  */
  116.  
  117. /* definition    number    opnd?    meaning */
  118. #define END    0    /* no    End of program. */
  119. #define BOL    1    /* no    Match "" at beginning of line. */
  120. #define EOL    2    /* no    Match "" at end of line. */
  121. #define ANY    3    /* no    Match any one character. */
  122. #define ANYOF    4    /* str    Match any character in this string. */
  123. #define ANYBUT    5    /* str    Match any character not in this string. */
  124. #define BRANCH    6    /* node Match this alternative, or the next... */
  125. #define BACK    7    /* no    Match "", "next" ptr points backward. */
  126. #define EXACTLY 8    /* str    Match this string. */
  127. #define NOTHING 9    /* no    Match empty string. */
  128. #define STAR    10    /* node Match this (simple) thing 0 or more times. */
  129. #define PLUS    11    /* node Match this (simple) thing 1 or more times. */
  130. #define OPEN    20    /* no    Mark this point in input as start of #n. */
  131.         /*    OPEN+1 is number 1, etc. */
  132. #define CLOSE    30    /* no    Analogous to OPEN. */
  133. #define BWORD    64    /* no    Beginning of word. */
  134. #define EWORD    65    /* no    End of word. */
  135.  
  136. /*
  137.  * Opcode notes:
  138.  *
  139.  * BRANCH    The set of branches constituting a single choice are hooked
  140.  *        together with their "next" pointers, since precedence prevents
  141.  *        anything being concatenated to any individual branch.  The
  142.  *        "next" pointer of the last BRANCH in a choice points to the
  143.  *        thing following the whole choice.  This is also where the
  144.  *        final "next" pointer of each individual branch points; each
  145.  *        branch starts with the operand node of a BRANCH node.
  146.  *
  147.  * BACK        Normal "next" pointers all implicitly point forward; BACK
  148.  *        exists to make loop structures possible.
  149.  *
  150.  * STAR,PLUS    '?', and complex '*' and '+', are implemented as circular
  151.  *        BRANCH structures using BACK.  Simple cases (one character
  152.  *        per match) are implemented with STAR and PLUS for speed
  153.  *        and to minimize recursive plunges.
  154.  *
  155.  * OPEN,CLOSE    ...are numbered at compile time.
  156.  */
  157.  
  158. /*
  159.  * A node is one char of opcode followed by two chars of "next" pointer.
  160.  * "Next" pointers are stored as two 8-bit pieces, high order first.  The
  161.  * value is a positive offset from the opcode of the node containing it.
  162.  * An operand, if any, simply follows the node.     (Note that much of the
  163.  * code generation knows about this implicit relationship.)
  164.  *
  165.  * Using two bytes for the "next" pointer is vast overkill for most things,
  166.  * but allows patterns to get big without disasters.
  167.  */
  168. #define OP(p)        (*(p))
  169. #define NEXT(p)     (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
  170. #define OPERAND(p)    ((p) + 3)
  171.  
  172. /*
  173.  * See regmagic.h for one further detail of program structure.
  174.  */
  175.  
  176.  
  177. /*
  178.  * Utility definitions.
  179.  */
  180. #ifndef CHARBITS
  181. #define UCHARAT(p)    ((int)*(unsigned char *)(p))
  182. #else
  183. #define UCHARAT(p)    ((int)*(p)&CHARBITS)
  184. #endif
  185.  
  186. #define FAIL(m)     { regerror(m); return(NULL); }
  187. #define ISMULT(c)    ((c) == '*' || (c) == '+' || (c) == '?')
  188. #define META        "^$.[()|?+*\\"
  189.  
  190. /*
  191.  * Flags to be passed up and down.
  192.  */
  193. #define HASWIDTH    01    /* Known never to match null string. */
  194. #define SIMPLE        02    /* Simple enough to be STAR/PLUS operand. */
  195. #define SPSTART        04    /* Starts with * or +. */
  196. #define WORST        0    /* Worst case. */
  197.  
  198. /*
  199.  * mkup - convert to upper case IF we're doing caseless compares
  200.  */
  201. #define mkup(c)        ((Pb(P_ignorecase) && is_lower(c)) ? \
  202.                         to_upper(c) : (c))
  203.  
  204. /*
  205.  * Global work variables for regcomp().
  206.  */
  207. static char *regparse;        /* Input-scan pointer. */
  208. static int regnpar;        /* () count. */
  209. static char regdummy;
  210. static char *regcode;        /* Code-emit pointer; ®dummy = don't. */
  211. static long regsize;        /* Code size. */
  212.  
  213. /*
  214.  * Forward declarations for regcomp()'s friends.
  215.  */
  216. #ifndef STATIC
  217. #    define    STATIC    static
  218. #endif
  219.  
  220. STATIC    char    *reg P((int paren, int *flagp));
  221. STATIC    char    *regbranch P((int *flagp));
  222. STATIC    char    *regpiece P((int *flagp));
  223. STATIC    char    *regatom P((int *flagp));
  224. STATIC    char    *regnode P((int op));
  225. STATIC    char    *regnext P((char *p));
  226. STATIC    void    regc P((int b));
  227. STATIC    void    reginsert P((int op, ch